/**
 * 插入排序
 插入排序有两个循环。外循环将数组元素挨个移动,而内循环则对外循环中选中的元素及它后面的那个元素进行比较。
 如果外循环中选中的元素比内循环中选中的元素小,那么数 组元素会向右移动,
 为内循环中的这个元素腾出位置,
 就像之前介绍的姓氏卡片一样。
 */
function insertSort() {
	var arr = new Array(6, 3, 0, 6, 5, 8, 7, 4, 2, 7);
	var tmp, len = arr.length;
	for (var i = 1; i < len; i++) {
		tmp = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > tmp) {
			arr[j+1] = arr[j];  // 元素后移，
			j--;
		}
		arr[j+1] = tmp;

		print(arr.toString());
	}
}

function bin_insertSort()  {
	var array = new Array(6, 3, 0, 6, 5, 8, 7, 4, 2, 7);
	var n = array.length;
    var i, j, temp, low, high, mid;  
    for(i = 1; i < n; ++i) {  
        temp = array[i];  //将当前需要被插入元素保存在temp中  
        low = 0;  
        high = i - 1;  
  
        while(low <= high)   //利用折半查找确定被插入元素array[i]的合适位置  
        {  
            mid = (low + high) / 2;  
            if(temp < array[mid])  
                high = mid - 1;  
            else  
                low = mid + 1;  
        }  
  
        for(j = i - 1; j >= low; --j)    //找到合适位置low, 将[low, i-1]中的元素依次后移一位  
            array[j + 1] = array[j];  
  
        array[low] = temp;    //插入元素array[i], 至此插入排序的一趟结束  

        print(array.toString());
    }  
} 

// insertSort();
bin_insertSort();